package com.duoduo.剑指Offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm
 * @description: 斐波那契数列14
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：1
 *
 * @author: chaidl  ！
 * @create: 2022-05-23 23:53
 */
public class 斐波那契数列14 {
	/**
	 * 动态规划
	 * @param n
	 * @return
	 */
	public int fib2(int n) {
		if (n == 0) {
		    return 0;
		}
		if (n == 1) {
		    return 1;
		}
		int a=0,b = 1;
		int result=0;
		for (int i = 2; i <= n; i++) {
			result=(a+b)%1000000007;
			a=b;
			b=result;
		}
		return result;
	}
	
	
	static Map<Integer,Integer> map = new HashMap<Integer, Integer>();
	
	/**
	 * 递归解法
	 * @param n
	 * @return
	 */
	public int fib(int n) {
		if (n==0){
			return 0;
		}
		if (n==1){
			return 1;
		}
	//	首先判断map里面有没有
		if (null!= map.get(n)){
			return map.get(n);
		}else {
			int tmp=(fib(n-1)+fib(n-2))%1000000007;
			map.put(n,tmp);
			return tmp;
		}
	}
}
